#include "DirTable.h"

namespace dataStructureZ
{
	using std::deque;
	using std::cout;
	using std::endl;
	
	template<class T1,class T2> class tupleIndex
	{
		public:T1 key;
		public:T2 val;
		
		public:tupleIndex<T1,T2>(void){}
		
		public:tupleIndex<T1,T2>
		(const T1&Key,const T2&Val):
		key(Key),val(Val){}
		
		public:tupleIndex<T1,T2>
		(const tupleIndex<T1,T2>&another):
		key(another.key),val(another.val){}
		
		public:tupleIndex<T1,T2>&operator = 
		(const tupleIndex<T1,T2>&another)
		{
			key = another.key;
			val = another.val;
			return*this;
		}
		
		public:bool operator==
		(const tupleIndex<T1,T2>&another)const
		{return(key==another.key);}
		
		public:bool operator!=
		(const tupleIndex<T1,T2>&another)const
		{return(key!=another.key);}
		
		public:bool operator>=
		(const tupleIndex<T1,T2>&another)const
		{return(key==another.key);}
		
		public:bool operator<=
		(const tupleIndex<T1,T2>&another)const
		{return(key<=another.key);}
		
		public:bool operator>
		(const tupleIndex<T1,T2>&another)const
		{return(key>another.key);}
		
		public:bool operator<
		(const tupleIndex<T1,T2>&another)const
		{return(key<another.key);}		
	};
	
	template<class T=char, class wgt=size_t>
	class huffmanTreeZ
	{
		protected:class node
		{
			friend class huffmanTreeZ<T, wgt>;
			
			protected:T		value;
			protected:wgt	weight;
			
			protected:node*	lChild;
			protected:node*	rChild;
			
			public:node(T elem=0, wgt Weight=0):value(elem), 
			weight(Weight), lChild(nullptr), rChild(nullptr){}
				
			public:node(const tupleIndex<wgt, T>& tpl):value(tpl.val), 
			weight(tpl.key), lChild(nullptr), rChild(nullptr){}
		};
		
		protected:node* root;
		protected:bool	revBit;
		
		/*
			true:	1 0
			false:	0 1
		*/
		
		protected:void freewow(node* now)
		{
			if(now != nullptr)
			{
				freewow(now->lChild);
				freewow(now->rChild);
				delete(now);
			}
		}
		
		public:void clear(void)
		{
			freewow(root->lChild);
			root->lChild = nullptr;
		}
		
		public:bool empty(void)
		{return root->lChild == nullptr;}
		
		public:~huffmanTreeZ(void)
		{freewow(root);}
		
		public:static inline bool
		minHeapCmp(const node* a, const node* b)
		{return a->weight > b->weight;}	
		
		public:huffmanTreeZ(bool bit_rev=false):
		root(new node), revBit(bit_rev){}
		
		public:huffmanTreeZ
		(
			const deque< tupleIndex<wgt, T> >& lst, 
			bool bit_rev = false
		):root(new node), revBit(bit_rev)
		{
			node* a,* b,* temp;
			deque<node*> que;
			
			for
			(
				class deque< tupleIndex<wgt, T> >::
					const_iterator i=lst.begin();
				i != lst.end();
				++i
			)	que.push_back(new node(*i));
			
			make_heap(que.begin(), que.end(), minHeapCmp);
			
			while(true)
			{
				a = que.front();
				pop_heap(que.begin(), que.end(), minHeapCmp);
				que.pop_back();
				b = que.front();
				pop_heap(que.begin(), que.end(), minHeapCmp);
				que.pop_back();
				
				temp = new node;
				temp->lChild = a;
				temp->rChild = b;
				temp->weight = a->weight + b->weight;
				
				if(!que.empty())
				{
					que.push_back(temp);
					push_heap(que.begin(), que.end(), minHeapCmp);
				}	else break;
			}
			
			root->lChild = temp;
		}
		
		public:huffmanTreeZ
		(
			ArrayBitController<uint8_t>* code, 
			bool bit_rev = false
		):	root(new node), revBit(bit_rev)
		{
			node* nowAt = nullptr;
			root->lChild = new node();
			
			for(uint8_t i=0 ; true ; ++i)							//for each code
			{
				nowAt = root->lChild;								//back to start node(root->lChild)
				for(uint8_t j=0 ; j<code[i].bitLen ; ++j)			//for each bit
				{
					if(bit_rev? code[i].get(j) : !code[i].get(j))
					{												//to left
						if(nowAt->lChild != nullptr)
							nowAt = nowAt->lChild;
						else nowAt = nowAt->lChild = new node();
					}
					else											//to right
					{
						if(nowAt->rChild != nullptr)
							nowAt = nowAt->rChild;
						else nowAt = nowAt->rChild = new node();
					}
				}
				nowAt->value = i;
				if(i == 255) break;
			}
		}
		
		protected:void bit_encode_(deque<uint8_t>& stk, node* now)
		{
			if(now != nullptr)
			{
				stk.push_back(revBit? 1 : 0);
				bit_encode_(stk, now->lChild);
				stk.pop_back();
				
				if(now->lChild==nullptr && now->rChild==nullptr)
				{
					printf("%x\t", (unsigned int)(now->value));
					for
					(
						deque<uint8_t>::iterator i=stk.begin();
						i != stk.end();
						++i
					)	printf("%u", (unsigned int)(*i));
					putchar('\n');
				}
				
				stk.push_back(revBit? 0 : 1);
				bit_encode_(stk, now->rChild);
				stk.pop_back();
			}
		}
		
		public:void bit_encode(void)
		{
			deque<uint8_t> stk;
			bit_encode_(stk, root->lChild);
		}
		
		protected:void bit_encode_(deque<uint8_t>& stk, node* now, ArrayBitController<uint8_t>* code)
		{
			if(now != nullptr)
			{
				stk.push_back(revBit? 1 : 0);
				bit_encode_(stk, now->lChild, code);
				stk.pop_back();
				
				if(now->lChild==nullptr && now->rChild==nullptr)
				{
					code[now->value].bitLen = stk.size();
					
					uint8_t byteLen = upDiv(code[now->value].bitLen, (uint8_t)8);
					code[now->value].data = new uint8_t[byteLen];
					
					uint8_t i=0;
					for
					(
						deque<uint8_t>::iterator j=stk.begin();
						j != stk.end();
						++j
					)	code[now->value].set(i++, *j);
				}
				
				stk.push_back(revBit? 0 : 1);
				bit_encode_(stk, now->rChild, code);
				stk.pop_back();
			}
		}
		
		public:void bit_encode(ArrayBitController<uint8_t> *code)
		{
			deque<uint8_t> stk;
			bit_encode_(stk, root->lChild, code);
		}
		
		protected:void preView_(node* now)
		{
			if(now != nullptr)
			{
				cout<<now->value<<endl;
				preView_(now->lChild);
				preView_(now->rChild);
			}
		}
		
		public:void preView(void)
		{preView_(root->lChild);}
		
		public:uint8_t readByte(ArrayBitController<uint64_t> buffer, uint64_t& readPtr)
		{
			node* nowAt = root->lChild;
			while(!(nowAt->lChild==nullptr && nowAt->rChild==nullptr))
			{
				if(revBit? buffer.get(readPtr++) : !buffer.get(readPtr++))
				{														//to left
					if(nowAt->lChild != nullptr)
						nowAt = nowAt->lChild;
					else throw "Decode fault.";
				}
				else													//to right
				{
					if(nowAt->rChild != nullptr)
						nowAt = nowAt->rChild;
					else throw "Decode fault.";
				}
			}
			return nowAt->value;
		}
	};
	
	#define fltwgt deque<tupleIndex<float, char>>
	//define add(x,y) push_back(tupleIndex<float, char>((x), (y)))
	#define fltwgt_t char, float
};
